package main

import (
	"container/list"
	"fmt"
)

//queue 实现
type Queue struct {
	Data *list.List
}

func (q *Queue) Push(data interface{}) {
	q.Data.PushBack(data)
}
func (q *Queue) Poll() interface{} {
	if q.Data.Len() == 0 {
		return nil
	}
	return q.Data.Remove(q.Data.Front())
}
func (q *Queue) IsEmpty() bool {
	return q.Data.Len() == 0
}
func (q *Queue) Size() int {
	return q.Data.Len()
}

func NewQueue() *Queue {
	return &Queue{
		Data: list.New(),
	}
}

//queue 实现 end

//二叉树 实现
type TreeNode struct {
	Left, Right *TreeNode
	Data        interface{}
}

func CreateBrinaryTreeByArr(arr []interface{}, index int) *TreeNode {
	if len(arr) == 0 || index >= len(arr) || arr[index] == nil {
		return nil
	}
	return &TreeNode{
		Left:  CreateBrinaryTreeByArr(arr, 2*index+1),
		Right: CreateBrinaryTreeByArr(arr, 2*index+2),
		Data:  arr[index],
	}
}

//二叉树 实现 end

func main() {
	arr := []interface{}{3, 9, 20, nil, nil, 15, 7}
	rootTree := CreateBrinaryTreeByArr(arr, 0)
	//fmt.Println(rootTree.Right.Right)
	//fmt.Println(rootTree.Left.Left)

	//求最小深度
	minDepth := GetMinTreeDepth(rootTree)
	fmt.Println("minDepth:", minDepth)
}

//广度优先算法-取最小深度
func GetMinTreeDepth(node *TreeNode) int {
	queue := NewQueue()
	queue.Push(node)
	var depth int = 1
	for !queue.IsEmpty() {
		lenTmp := queue.Size()
		for i := 0; i < lenTmp; i++ {
			if curl, ok := queue.Poll().(*TreeNode); ok {
				if curl.Left == nil && curl.Right == nil {
					return depth
				}
				if curl.Left != nil {
					queue.Push(curl.Left)
				}
				if curl.Right != nil {
					queue.Push(curl.Right)
				}
			}
		}
		depth++
	}
	return depth
}
